• 原文：BLS12-381 For The Rest Of Us
• 作者：Ben Edgington
• 译者：Kurt Pan

开始鼓捣之前，我希望我知道的。 近年来，椭圆曲线BLS12-381逐渐火了起来。许多协议都将其应用到了数字签名和零知识证明中：Zcash、Ethereum 2.0、Skale、Algorand、Dfinity、Chia 等等。 不幸的是，现有的关于 BLS12-381 的资料里充满着晦涩的咒语，比如“实例化其六度扭”和“最优扩张域塔”。我就是来解决这个问题的 ¹ 我不会对椭圆曲线及其令人兴奋的群的性质进行一般性介绍。这方面已经有一些很棒的入门资料了，我将假设读者具有这些基础知识。当然，这里的很多内容并非只特定于 BLS12-381，而是也适用于其他曲线。

动机

BLS12-381 是一个配对友好的椭圆曲线。

基于配对的密码学在过去几十年得到了很大发展，使得很多有用的新应用成为了可能，例如可高效聚合的短数字签名、基于身份的密码学、单轮多方密钥交换和高效的多项式承诺方案（如KZG承诺）。

配对友好的椭圆曲线是具有良好的嵌入度（将在下文解释！）和大素数阶子群（也见下文）的曲线。这些曲线很少见。如果你随机创建一条椭圆曲线，它是配对友好的可能性会非常之小。然而，它们确实是可以构造出来的， BLS 曲线就是被显式构造为配对友好的。还有其他几个配对友好曲线簇。

关于曲线BLS12-381本身

历史

曲线 BLS12-381是由Sean Bowe在 2017 年初作为一次 Zcash 协议升级的基础内容设计的。它既对配对友好（使其对数字签名高效）又对构造 zkSnarks 高效。

“下一代”、可扩展区块链协议的激增使得生成可以高效聚合以及可以轻松门限化的短数字签名变得非常重要。BLS12-381 的性质使其经常成为这些协议的首选曲线。

一些密码学库——Apache 的Milagro等成熟库，以及Herumi和Blst等新兴库——都支持 BLS12-381。并且已经有将 BLS12-381 纳入 IETF 标准的举措，例如Pairing-Friendly Curves、Hashing to Elliptic Curves和BLS signatures。这对于协议互操作性来说是个好消息！

命名

BLS12-381 是Barreto、Lynn 和 Scott描述的曲线簇的一部分（他们就是是此处的 B、L 和 S -稍后将出现不同的 BLS 三人组）。

12 是曲线的嵌入度：既不太低也不太高。稍后我们将讨论嵌入度。

381是表示曲线上坐标所需的比特数：域模数，$q$。 一个点的坐标来自一个具有素数阶的有限域，而那个素数，$q$, 是 381 比特。381 是一个相当方便的数字，因为我们可以为每个域元素使用 48 个字节，剩下 3 比特用于有用的标志或算术优化。这个数字的大小取决于安全要求和实现效率。

曲线方程和参数

BLS12-381曲线的基础方程是$y^2=x^3+4$。

一条BLS 曲线的关键参数是由单个参数 $\mathbf{x}$ （与曲线方程中的 $x$ 不同！）来设置的，可以通过选择该参数来为曲线提供对实现良好的性质。 BLS12-381 源自“分类法”论文中构造 6.6 的 $k \equiv 0(\bmod 6)$ 的情况。

BLS12-381 的具体设计目标如下：

• $\mathbf{x}$ 具有“低汉明权重”，即只有很少的位设置为1 。 这对于计算配对算法（米勒循环）的效率尤其重要。
• 上面提到的域模数 $q$ 是质数且具有 383 位或更少，这使得在其上进行 64 位或 32 位算术更加高效。
• 使用的子群的阶 $r$ 是质数且具有 255 位或更少，与上面的原因相同。
• 安全目标是 128 比特 - 见下文。
• 为了支持 zkSnark 方案，我们希望在 $F_r$ 域中具有大2的幂的单位根。 即对于一些较大的 $n$，我们希望 $2^n$ 成为 $r-1$ 的因子。 （使 $\mathrm{x}$ 为 $2^{\frac{n}{2}}$ 的倍数即可实现此目的。）该性质是能够使用快速傅立叶变换来实现多项式乘法等有趣事物的关键。

值 $\mathbf{x}=$ -0xd201000000010000 （十六进制，注意它是负数）给出了满足这些条件的最大 $q$ 和最低汉明权重。 有了这个 $\mathbf{x}$ 值，我们就有，

本节大部分内容的参考。 IETF 标准中也包含大量曲线数据。

域扩张

域扩张是椭圆曲线配对的基础。 BLS12-381中的“12” 不仅是嵌入度，也是需要使用的（相对）域扩张度。

可以认为域$F_q$只是整数模 $q: 0,1, \ldots, q-1$。 但 $F_{q^{12}}$ 是什么鬼，$F_q$ 的第十二个扩张吗？

我没在任何地方找到任何简单的关于域扩张的解释，以下是我在努力理解一段时间后的尝试。

我们来构造一个 $F_{q^2}$，$F_q$ 的二次扩张。 在 $F_{q^2}$ 中，我们将域元素表示为一次多项式，比如 $a_0+a_1 x$，如果愿意也可以更简洁地写为 $\left(a_0, a_1\right)$。

两个元素相加很容易： $(a, b)+(c, d)=a+b x+c+d x=(a+c)+(b+d) x=$ $(a+c, b+ d)$。 只需确保约简$a+c$ 和 $b+d$ 模 $q$。

相乘呢？ $(a, b) \times(c, d)=(a+b x)(c+d x)=a c+(a d+b c) x+b d x^2=???$。 糟糕 - 我们应该如何处理 $x^2$ 系数呢？

We need a rule for reducing polynomials so that they have a degree less than two. In this example we’re going to take $x^2+1=0$ as our rule, but we could make other choices. There are only two rules about our rule ${ }^{[2]}$ :

1. it must be a degree $k$ polynomial, where $k$ is our extension degree, 2 in this case; and
2. it must be irreducible in the field we are extending. That means it must not be possible to factor it into two or more lower degree polynomials. Applying our rule, by substituting $x^2=-1$, gives us the final result $(a, b) \times(c, d)=$ $a c+(a d+b c) x+b d x^2=(a c-b d)+(a d+b c) x=(a c-b d, a d+b c)$. This might look a little familiar from complex arithmetic: $(a+i b) \times(c+i d)=(a c-b d)+(a d+b c) i$. This is not a coincidence! The complex numbers are a quadratic extension of the real numbers.

我们需要一个规则来约简多项式，使其次数小于二。 此例中，我们将采用 $x^2+1=0$ 作为该规则，但也可以做出其他选择。 关于我们的规则 ${ }^{[2]}$ 只有两条规则：

1. 它必须是一个 $k$ 次多项式，其中 $k$ 是我们的扩展度，在本例中为 2； 和
2. 在扩张的域中必须是不可约的。 这意味着不可能将它分解为两个或多个较低次数的多项式。 应用我们的规则，通过代入 $x^2=-1$，得到最终结果 $(a, b) \times(c, d)=$ $a c+(a d+b c) x+b d x^2= (a c-b d)+(a d+b c) x=(a c-b d, a d+b c)$。 从复杂的算术来看，这可能看起来有点熟悉：$(a+i b) \times(c+i d)=(a c-b d)+(a d+b c) i$。 这不是巧合！ 复数是实数的二次扩展。

两条曲线

子群

扭

但还有另一个挑战。 正如前面所讨论的，在 $F_{q^{12}}$ 中进行算术运算非常复杂且效率低下，而且曲线运算需要大量的算术运算。 看起来这就是卡住我们的地方。

真的这样吗？嗯，这里故事有一个转折… ²

扭（twist）类似于坐标变换。 更奇妙的是，可以用来将我们的 $E\left(F_{q^{12}}\right)$ 曲线转换为在仍具有阶 $r$ 的子群的低阶域上定义的曲线。 此外，这个子群与我们的 $G_2$ 群 ³ 之间有一个简单的映射。

BLS12-381 使用“六度扭”（sextic twist），意思是它将扩张域的阶降低了六倍。 因此扭曲线上的 $G_2$ 可以通过 $F_{q^2}$ 而不是 $F_{q^{12}}$ 来定义，这大大节省了复杂性。

我还没有在任何地方看到这个被写下来 - 但这里的第 3 节在试图进行解释 - 如果我们找到一个 $u$ 使得 $u^6=(1+i)^{-1}$ ，那么我们可以定义扭变换为$(x, y) \rightarrow\left(x / u^2, y / u^3\right)$。 这会将原始曲线 $E: y^2=x^3+4$ 转换为曲线 $E^{\prime}: y^2=x^3+4 / u^6=x^3+4(1 +i）$。 $E$ 和 $E^{\prime}$ 看起来不同，但实际上是针对不同基域 ⁴ 中的系数呈现的同一对象。

当扭正确完成时，得到的 $E^{\prime}$ 具有一个 $r$ 阶子群，映射到我们的 $G_2$ 群，反之亦然。 因此，事实证明，在大多数情况下，我们可以在 $E^{\prime}$ 上使用 $F_{q^2}$ ，并仅在需要时（即实际计算配对时）将 $G_2$ 映射回 $E\left(F_{q^{12} }\right)$ 。

这是我们将使用的两个群：

• $G_1 \subset E\left(F_q\right)$ 其中 $E: y^2=x^3+4$
• $G_2 \subset E^{\prime}\left(F_{q^2}\right)$ 其中 $E^{\prime}: y^2=x^3+4(1+i)$

这就是为什么 BLS12-381 看起来像两条曲线，而不是一条曲线的原因。

注意$G_1$ 群中的点的坐标是一对整数，$G_2$ 群中的点的坐标是一对复数，因此 $G_2$ 的点占用两倍的存储量，工作成本更高 。这导致了有趣的实现中的权衡。

配对

所以这个配对到底是怎么回事呢？

就 BLS12-381 而言，配对就是取点 $P \in G_1 \subset E\left(F_q\right)$ 和点 $Q \in G_2 \subset E^{\prime}\left (F_{q^2}\right)$ ，并输出群 $G_T \subset F_{q^{12}}$ 中的一个点。 也就是说，对于配对 $e$， $e: G_1 \times G_2 \rightarrow G_T$

配对通常表示为 $e(P, Q)$ 并且具有一些特殊性质。 我不会去详细介绍所有细节（我们几乎可以将它们视为黑盒），Vitalik 的文章提供了很好的介绍，而对于所有精彩的细节，让我再次推荐“Pairings For Beginners”。

我们感兴趣的是：

• $e(P, Q+R)=e(P, Q) \cdot e(P, R)$，且
• $e(P+S, R)=e(P, R) \cdot e(S, R)$

由此，我们可以推断出以下所有等式都成立：

• $e([a] P,[b] Q)=e(P,[b] Q)^a=e(P, Q)^{a b}=e(P,[a] Q)^b= e([b] P,[a] Q)$. ⁵

这正是我们验证数字签名时所需要的。

如果有帮助，你可以大致将配对视为将 $G_1$ 中的点“乘以”$G_2$ 中的点的一种方法。 如果所有群都用加法符号，那么算术就会很好地运转。 然而我们通常将 $G_T$ 用乘法表示，因此这种表示法并不太正确。

嵌入度

我们已经多次提到嵌入度，它的重要性使得它足以出现在曲线的名称中。

嵌入度 $k$ 为使 $r$ 整除 $\left(q^k-1\right)$ 的最小正整数。 因此，在 BLS12-381 的情况下，$r$ 是 $\left(q^{12}-1\right)$ ⁶ 的因子，但不是任何更低幂的因子。

事实证明，这个数字给出了满足两个等价条件的最小域扩张 $F_{q^k}$：

• $F_{q^k}$ 包含多个 $r$ 阶子群（用于构造 $G_2$，见上文）；
• $F_{q^k}$ 包含所有 $r$ 次单位根（用于构造 $G_T$，见下文）

这些是使得配对成为可能必须满足的条件。

嵌入度的选择是安全和效率之间的平衡（一如既往）。 安全方面，嵌入度也称为安全乘子：较高的嵌入度使得$G_T$中的离散对数问题更难解决。 然而，高嵌入度意味着我们必须在高阶扩展，例如$F_{q^{12}}$，中进行域操作，这是笨重且低效的。 （即使使用扭也是如此：最大可用扭为六度，因此我们能做的最好的是将域扩张度减少六倍。并且无论如何，配对必须在大扩张域中完成。）

12 或 24 的嵌入度似乎是当前许多应用的最佳选择。 再次强调，BLS12-381 的嵌入度就是名称中的12。

安全级别

密码系统的安全性是以比特来衡量的。非正式地，我将 $n$ 比特安全性理解为“需要大约 $2^n$ 个操作才能破解”。

对于椭圆曲线密码学，安全性就是要使离散对数问题困难。 也就是说，给定一个点 $g$ 和一个点 $g^k$（以乘法群表示），在没有先验知识的情况下找到 $k$ 必定是不可行的。 也就是说，至少需要 $2^n$ 次操作才能实现此目的，按今天的说法，$n>100$ 左右。

对于配对友好的曲线，离散对数问题在我们使用的三个群中的每一个中都必须是困难的。 因此，为了实现 $n$ 比特安全性，

• 素数群阶 $r$ 必须至少为 $2 n$ 位长，因为有些算法（例如 Pollard 的 rho 算法）的开销为 $O(\sqrt{r})$。
• 扩张域 $F_{q^k}$ 必须足够大，以免受到数域筛法等方法的影响。

BLS12-381 旨在根据这些原则提供大约 128 比特的安全级别，这得到了初步分析的支持。 例如，请参见分类法论文中的表 1.1。

然而，经过仔细检查，按照上述第二个标准，“大小为 $3072=12 \times 256$ 位的有限扩张域似乎不够大”（引用这里的第 2 节）。

根据 NCC Group 引用其他来源的一份报告，实际安全级别可能在 117 到 120 比特之间（参见第 8 页）。 他们认为这是一个完全足够的安全级别：“达到‘128 比特’的价值主要是心理上的”。 Sean Bowe 还根据最初的设计目标对安全级别进行了评论。

协因子

一个子群的协因子是整个群的大小和子群大小的比。平常的椭圆曲线密码学要求协因子非常小，通常为一，以避免对离散对数的小子群攻击。 然而在基于配对的密码学中，情况并非如此，$G_1$ 和 $G_2$群的协因子可能会非常大。

事实证明，只要小心，我们可以在拥有大协因子的同时依然安全。 即当$G_1, G_2$和$G_T$的协因子不包含小于$r$的素因子时。这篇论文的3.2节对此进行了详细讨论。然而这并非BLS12-381的情况 ，$G_1$ 和 $G_2$ 的协因子都有一些小因子。 因此，我们必须在实现中小心小子群攻击。

作为参考，$G_1$ 和 $G_2$ 的协因子如下。

这一切意义何在？ 事实证明，乘以协因子是将椭圆曲线上的任意点映射到相应子群 $G_1$ 或 $G_2$ ⁷ 的直接方法。 这在进行“哈希到曲线”等操作时很重要：我们首先在曲线上取一个点，然后通过乘以协因子（所谓的协因子清除）将其映射到正确的群里。

单位根

这里是一个关于单位根的注释，因为它们出现在两个完全不同且不相关的上下文中，这可能会令人困惑。

First, we said that to support zkSnark schemes with this curve, for some biggish $n$ we want to have a $2^n$ th root of unity in the field $F_r$ (not $F_q$, note). This is to facilitate efficient fast Fourier transforms for manipulating very large polynomials over the scalar field $F_r$. From the hexadecimal representation of $r-1$, it’s clearly a multiple of $2^{32}$, so there is a $2^{32}$ th root of unity $\left(2^{32}\right.$ of them, in fact). Job done,

首先，我们说，为了用这条曲线支持 zkSnark 方案，对于一些较大的 $n$，我们希望在域 $F_r$ 中有一个 $2^n$ 单位根（注意，不是 $F_q$）。 这是为了促进高效的快速傅里叶变换，以在标量域 $F_r$ 上操作非常大的多项式。 从$r-1$的十六进制表示来看，它显然是$2^{32}$的倍数，因此存在$2^{32}$的统一根$\left(2^{32}\right.$ 事实上，其中）。 任务完成，

Second, and completely unrelated, the effect of the pairing is to map the two points from $G_1$ and $G_2$ onto an $r$ th root of unity in $F_{q^{12}}$. These $r$ th roots of unity actually form a subgroup in $F_{q^{12}}$ of order $r^{[14]}$, which is the group we call $G_T$.

Let’s briefly revisit our discussion of extending the base field for $E$ to $F_{q^{12}}$, which we did in order to find another subgroup of order $r$. It also turns out $F_{q^{12}}$ treated as a multiplicative group is the smallest field extension that contains the $r$ th roots of unity in the field, the 12 coming from the embedding degree once again. This is why $G_T$ is defined over $F_{q^{12}}$.

曲线BLS12-381的使用

BLS数字签名

现在是介绍另一个 BLS 的时候了：Boneh、Lynn 和 Shacham。（L 与 BLS12-381 中的 L 是一个人；B 和 S 不是。）

BLS 签名于 2001 年提出，比 2002 年BLS 曲线系列发布稍早一些。令人高兴的是，它们是携手共进的关系。（BLS 签名可以使用其他曲线；BLS 曲线也有签名以外的用途。但是当它们结合在一起时就挺不错。）

IETF 标准草案中对 BLS 签名方案有相当简洁明了的描述。另请参阅该GitHub 库。

公私钥

私钥（用于签名）就是一个1到$r-1$之间随机选择的一个数，称之为$sk$。

相应的公钥（如果我们对公钥使用$G_1$）为$p k=[s k] g_1$，其中$g_1$为对$G_1$选择的生成元。即用$s k$乘上$g_1$，就是把$g_1$ 自己相加$s k$次。

离散对数问题的意思是给定公钥$p k$恢复$s k$是不可行的。

签名

要对消息 $m$ 签名，我们首先需要将 $m$ 映射到群 $G_2$ 中的一个点（如果我们使用 $G_2$ 进行签名的话）。 对此实现方法的讨论，请参阅下面的哈希到曲线。 现在假设已经可以做到这一点，并将所得的 $G_2$ 上的点称为 $H(m)$。

我们通过计算签名$\sigma=[s k] H(m)$来对消息进行签名， 即是用私钥乘上哈希点。

验证

给定消息 $m$、签名 $\sigma$ 和公钥 $p k$，我们想要验证它是否是用与 $p k$ 对应的 $s k$ 签名的。

这就是要用到配对的地方了。当且仅当 $e\left(g_1, \sigma\right)=e(p k, H(m))$ 时，签名才有效。

我们可以用配对的性质来确认这一点：

\(e(p k, H(m))=e\left([s k] g_1, H(m)\right)=e\left(g_1, H(m)\right)^{(s k)}=e\left(g_1,[s k] H(m)\right)=e\left(g_1, \sigma\right)\)

聚合

BLS 签名的一个非常好的特性是它们是可以聚合的（另请参阅原始论文），因此我们只需要两个配对来验证 $n$ 方签名的单个消息，或 $n+1$ 个配对来验证由 $n$ 方签名的 $n$ 条不同消息，而不是你可能天真地期望需要的 $2 n$ 个配对。 配对的计算成本很高，因此这非常有吸引力。

可以聚合不同消息上的签名，或同一消息上的签名。 对于以太坊 2.0 我们聚合相同的消息，因此为了简洁起见这里只考虑这种情况。

要聚合签名，我们只需将它们对应的 $G_2$ 点相加即可：$\sigma_{a g g}=\sigma_1+\sigma_2+\ldots+\sigma_n$。 我们还聚合了对应的$G_1$公钥点 $p k_{a g g}=p k_1+p k_2+\ldots+p k_n$

现在配对的魔法意味着我们可以通过验证 $e\left(g_1, \sigma_{a g g}\right)=e\left(p k_{a g g}, H(m)\right)$ 来验证所有的签名，总共仅包含两个配对。

恶意密钥攻击

正如这里面的 1.1 节所述，当聚合同一消息的签名时，我们需要去注意可能的“恶意公钥攻击”（Rogue public key attack）。

假设你的公钥是 $p k_1$，而我有一个私钥 $s k_2$。 但我没有发布我的真实公钥，而是发布 $p k_2^{\prime}=\left[s k_2\right] g_1-p k_1$ （即我的真实公钥加上你的公钥的逆）。 我可以用我的私钥签名消息 $H(m)$ ，生成 $\sigma=\left[s k_2\right] H(m)$。 然后我发布声明，声称这是你和我共同签署的聚合签名，聚合公钥是 $p k_{a g g}=p k_1+p k_2^{\prime}$。

在验证时，我的声明就得到了验证：在你实际没有时看起来你参与了对消息的签名。： $e(g 1, \sigma)=e\left(g_1,\left[s k_2\right] H(m )\right)=e\left(\left[s k_2\right] g_1, H(m)\right)=e\left(p k_1+p k_2^{\prime}, H(m)\right)$

对此的一种相对简单的防御措施（在以太坊 2.0 中使用的防御措施）是强制验证者注册与其所声称的公钥相对应的私钥的“拥有证明”。 这里你也可以看到，攻击者是没有与$p k_2^{\prime}$对应的$s k_2^{\prime}$的。 这可以简单地通过让验证者在注册时对其公钥签名来完成：如果签名可以使用该公钥进行验证，那么一切就都好。

可以使用更复杂的方案，不需要私钥知识证明 (KOSK)。

G1和G2对调

对于数字签名的目的来说，$G_1$ 和 $G_2$ 群是可以对调的。 我们可以选择公钥作为 $G_1$ 的成员，签名作为 $G_2$ 的成员，反之亦可。

权衡点是执行速度和存储大小。 $G_1$的点小且速度快； $G_2$ 的点大且速度慢。 BLS12-381 最初是为了实现 Zcash 而设计的，出于性能原因，他们选择使用 $G_1$ 来表示签名，使用 $G_2$ 来表示公钥。

大多数其他实现都是和Zcash“相反的”。 在以太坊 2.0 中，我们使用 $G_1$ 作为公钥：一方面，公钥聚合比签名聚合发生得更频繁； 另一方面，验证器的公钥需要以状态存储，因此保持较小的表示很重要。 那么签名自然就是 $G_2$ 的点。

点压缩

注意，有时扭操作也被称为点压缩 - 这与我们在这里讨论的完全不是一回事。

为了存储和传输椭圆曲线点，通常会删除 $y$ 坐标。 这使得数据量减半。 对于 BLS12-381，$G_1$ 的点从 96 字节 ($2 \times 381$ 比特四舍五入到字节) 减少到了 48 字节，$G_2$ 的点从 192 字节减少到 96 字节。

任何椭圆曲线点都可以通过使用相关的曲线方程 $E$ 或 $E^{\prime}$ 从 $x$ 坐标来重新生成。 对于曲线上任何有效的 $x$ 坐标，$y$ 要么为零，要么具有两个互为负的可能值：对于 $G_1$，$y= \pm \sqrt{x^3+4}$， $G_2$ 也类似。

由于域元素为 381 位，而 48 字节为 384 位，因此我们有一些空闲位用于标记。 最重要的一个标志用于显示该点对应于哪个 $y$ 值（正值或负值）。 另一位用于表示这是否是无穷远点（无穷远点有许多可能的表示）。 第三个标记位只是简单地指示这是压缩的还是未压缩的表示，尽管在实践中上下文应当会处理这点。

对于 $G_1$ 和 $G_2$ 来说，大约一半的 $x$ 值不在曲线上。 在这种情况下，该点通常被解码为无穷远点。 但除非设置了无穷标志位——这种情况下我们不会尝试解码该点——这是一个错误条件。

标志位和$x$值如何编码的具体细节见这里。

子群成员检验{#subgroupcheck}

当处理任何来源未知的点时，无论它是压缩的还是未压缩的，很重要的一点是去检查它是否位于正确的子群中。 上面描述的点解压缩只是得到了曲线上的一个点； 我们不知道它是否位于正确的$G_1$或$G_2$中。

主要的问题似乎在于 $E\left(F_q\right)$ 和 $E^{\prime}\left(F_{q^2}\right)$ 都包含小子群（你可以通过分解协因子来看到这点，例如使用此工具。） 正如这篇论文所讨论的，无意中使用这些小子群中的点可能会导致漏洞。

原则上子群检验很简单：只需将我们的点乘以 $r$ 即可。 对于 $G_1$ 或 $G_2$ 中的点，结果为相应的无穷远点； 对于这些群之外的点，则不会。

不幸的是，这在实践中很慢，特别是对于 $G_2$，因为 $r$ 太大了。 作为替代方案，有一些新技术利用自同态来执行更快的子群检验。

生成元

$G_1$ 和 $G_2$ 是素数阶循环群，因此任何点（除了单位元/无穷远点）都是生成元。 因此，选定生成元只是惯例上的考虑。

$G_1$ 和 $G_2$ 的生成元点在这里以十进制给出，相同的点在这里以十六进制给出。

这些是根据如下选定的：

$G_1$ 和 $G_2$ 的生成元是通过查找字典序最小的有效 $x$ 坐标及其字典序最小的 $y$ 坐标并通过协因子对其进行缩放来计算的，以便结果不是无穷远点。

根据我的计算，$h_1$ 和 $h_2$ 分别为相应群的协因子时，这使得 $G_1$ 生成元 $g_1=\left[h_1\right] p_1$，其中 $p_1$ 如下，

p1 = (0x04, 0x0a989badd40d6212b33cffc3f3763e9bc760f988c9926b26da9dd85e928483446346b8ed00e1de5d5ea93e354abe706c)

且$G_2$的生成元$g_2=\left[h_2\right] p_2$，其中$p_2$如下，

p2 = ([0x02, 0x00],[0x013a59858b6809fca4d9a3b6539246a70051a3c88899964a42bc9a69cf9acdd9dd387cfa9086b894185b9a46a402be73,0x02d27e0ec3356299a346a09ad7dc4ef68a483c3aed53f9139d2f929a3eecebf72082e5e58c6da24ee32e03040c406d4f])

我认为“字典序最小”意思是将基域中的所有数视为非负数，并且只取较小的数字，优先考虑实部而不是虚部。

最终指数

Calculation of a pairing has two parts: the Miller loop and the final exponentiation. Both are quite expensive, but there’s a nice hack you can do to reduce the impact of the final exponentiation. Normally, we calculate two full pairings in order to perform signature verification, to check whether $e\left(g_1, \sigma\right)=e(p k, H(m))$.

If we denote as $e^{\prime}(\cdot, \cdot)$ the pairing without the final exponentiation, then for, some $x$, we are checking whether $e^{\prime}\left(g_1, \sigma\right)^x=e^{\prime}(p k, H(m))^x$. ( $x$ happens to be $\left(q^k-1\right) / r$, which is huge.) We know how to multiply in group $G_T$, so we can reorganise this as a check whether $\left(e^{\prime}\left(-g_1, \sigma\right) e^{\prime}(p k, H(m))\right)^x=1$. (We can negate any one of the points: the magic of pairings makes this equivalent to taking the inverse in $G_T$.) So, to verify a signature, we do the two Miller loops, one with a negated input value, multiply the results and then do a single final exponentiation. If the result is unity in $G_T$ then our pairings match. This ought to give a worthwhile speedup.

配对的计算分为两个部分：米勒循环（Miller loop）和最终指数（final exponentiation）。 两者都相当昂贵，但是可以采取一些不错的技巧来减少最终指数的影响。

通常我们会计算两个完整的配对来进行签名验证，检查是否$e\left(g_1, \sigma\right)=e(p k, H(m))$。

如果我们将没有最终指数的配对表示为 $e^{\prime}(\cdot, \cdot)$，那么对某个 $x$，我们检查是否 $e^{\prime}\left(g_1, \sigma\right)^x=e^{\prime}(p k, H(m))^x$。 （ $x$ 恰好为 $\left(q^k-1\right) / r$，这很大的。）

我们知道如何在群 $G_T$ 中相乘，因此我们可以将其重新组织为检查是否 $\left(e^{\prime}\left(-g_1, \sigma\right) e^{\prime}(p k, H(m))\right)^x=1$。 （我们可以否定任何一点：配对的魔力使得这相当于在 $G_T$ 中取逆。）

因此，为了验证签名，我们执行两个米勒循环，其中一个具有负输入值，将结果相乘，然后进行一次最终求幂。 如果 $G_T$ 的结果是一致的，那么我们的配对匹配。 这应该会带来值得的加速。

哈希到曲线

哈希并检验

Simplified SWU map

协因子清除

We discussed multiplying by the cofactor as a way to make an arbitrary point on $E$ or $E^{\prime}$ into a point in $G_1$ or $G_2$ respectively. This is useful when hashing to the curve, for example. The $G_2$ co-factor is huge, so multiplying by it is slow. However, there are faster ways to map curve points into $G_2$ using an endomorphism (a map of a group to itself). This features in the new standard (see section 7). The endomorphism we want to use was subject to a patent, but this has now expired everywhere. As a workaround to the patent, instead of multiplying by the $G_2$ cofactor, the standard suggests multiplying by an effective cofactor (see section 8.9.2 for the value) which gives the same result as the endomorphism. The effective cofactor is even larger than the $G_2$ cofactor, but the multiplication can be implemented using an addition chain as an optimisation. The idea is that, now that the patent has expired, the endomorphism can be just dropped in as a replacement for the effective cofactor multiplication.

扩展塔

坐标系

求域元素的逆（即除法）是一项昂贵的操作，因此椭圆曲线算术的实现会尽可能避免该操作。 如果我们选择正确的坐标系来表示点，这会有所帮助。

仿射坐标

仿射坐标是点的传统表示形式，就是坐标对$(x,y)$，其中$x$和$y$满足曲线方程。 这是我们在存储和传输点时所通常使用的。

标准射影坐标

However, it is not always the most efficient form to use when actually working with points, and there are two other schemes I’m aware of that are used for BLS12-381.

The basic idea is to represent the coordinate using notional fractions, reducing the number of actual division operations needed. To do this, a third coordinate is introduced and we use $(X, Y, Z)$ for the internal representation of a point. Like our familiar fractions, there are many representations of the same value, all corresponding to a single actual value $\left(\frac{1}{2}, \frac{3}{6}, \frac{197}{394}\right.$ are all the same number). The two systems I know of in use for BLS12-381 are Standard Projective coordinates and Jacobian coordinates.

然而，在实际处理点时，它并不总是最有效的形式，而且我知道还有两种用于 BLS12-381 的方案。

基本思想是使用概念分数来表示坐标，从而减少实际所需除法运算的数量。 为此，引入了第三个坐标，我们使用 $(X, Y, Z)$ 作为点的内部表示。 就像我们熟悉的分数一样，同一个值有多种表示形式，都对应于一个实际值 $\left(\frac{1}{2}, \frac{3}{6}, \frac{197}{394 }\right.$ 都是相同的数字）。 据我所知，BLS12-381 使用的两个系统是标准射影坐标和雅可比坐标。

Jacobian 坐标

A different kind of projective coordinates are Jacobian coordinates. In this scheme, the Jacobian point $(X, Y, Z)$ represents the Affine point $\left(X / Z^2, Y / Z^3\right)$. The curve equation becomes $Y^2=X^3+4 Z^6$

The sample code for the constant-time hash-to-curve uses Jacobian coordinates under the hood.

Note that, in both schemes, the easiest way to import the Affine point $(x, y)$ is to map it to $(x, y, 1)$

进一步阅读资源

上面已经有了很多参考链接，这里就不重复了。 我只会挑一些特别有用或有趣的。

有用的参考资料：

• 原始BLS12-381的发布
• 参数和序列化的简洁描述
• IETF 标准草案
• 一个上述内容的太长不看版：给大忙人的BLS

一般来说，配对库的实现往往是高度优化的且/或非常通用的（支持多曲线），这使得很难去学。 Paul Miller 使用 JavaScript/TypeScript 编写的 Noble BLS12-381 库绝对是最容易理解的库之一。

最后，还有一些有趣的读物：

• 这份关于 Curve9769 的全新白皮书与 BLS12-381 没有直接关系，但它是对设计和实现椭圆曲线（此例中不是配对友好的）的苦与乐写得很好的精彩探索。
• 配对没有死，只是在休息。 一个很好的概述介绍。 有一些 BLS12-381 的东西。

就这样吧，朋友们拜拜！